// 767. 重构字符串
function reorganizeString(S: string): string {
    let cnt = new Array(26).fill(0)
    const base = 'a'.charCodeAt(0)
    let max = 0
    for(let c of S){
        if(++cnt[c.charCodeAt(0)-base]>max)max = cnt[c.charCodeAt(0)-base]
    }
    if(max>Math.ceil(S.length/2)) return ''
    let set = new Set<number>()
    cnt.forEach((v,i)=>{
        if(v!=0) set.add(i)
    })    
    //假装用了优先队列
    let strArr:string[] = []
    while(set.size>1){
        let m1 = 0
        let i1 = -1
        let m2 = 0
        let i2 = -1
        for(let i of set){
            const v = cnt[i]
            if(v>m1){
                m2 = m1
                i2 = i1
                m1 = v
                i1 = i
            }else if(v>m2){
                m2 = v
                i2 = i
            }
        }
        strArr.push(String.fromCharCode(base+i1))
        strArr.push(String.fromCharCode(base+i2))
        if(m1==1){
            set.delete(i1)
        }else{
            cnt[i1]--
        }
        if(m2==1){
            set.delete(i2)
        }
        else{
            cnt[i2]--
        }
    }
    //最后还有可能有一个
    for(let i of set){
        strArr.push(String.fromCharCode(base+i))
    }
    return strArr.reduce((pre,cur)=>pre+cur,'')
};

console.log(reorganizeString(''))